package com.fanshuai.algorithms.datastructure.linear;

import com.fanshuai.stack.LinkedStack;
import com.fanshuai.stack.Stack;

import java.util.HashMap;
import java.util.Map;

/**
 * 计算器 支持+, -, *, /, ^，不支持括号
 */
public class Calculator {
    private Stack<Integer> dataStack; //操作数栈
    private Stack<Character> opStack;    //运算符栈

    /**
     * 操作符优先级  + - 为1；  * / 为2；  ^ 为3
     */
    private Map<Character, Integer> opLevel = new HashMap<>();

    public Calculator() {
        dataStack = new LinkedStack<>();
        opStack = new LinkedStack<>();

        opLevel.put('+', 1);
        opLevel.put('-', 1);
        opLevel.put('*', 2);
        opLevel.put('/', 2);
        opLevel.put('^', 3);
    }

    public void clear() {
        dataStack = new LinkedStack<>();
        opStack = new LinkedStack<>();
    }

    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }

    /**
     * 根据表达式计算值 表达式有数字，+, -, *, /, ^，不支持括号
     *
     * 首先提取操作数，操作数为连续的数字字符，然后将操作数压入操作数栈
     * 然后根据操作符优先级做响应的操作:
     * （1）运算符栈为空，或者当前操作符优先级大于栈顶操作符优先级，运算符压入运算符栈
     * （2）当前操作符优先级小于等于栈顶操作符优先级，弹出操作数栈顶2个元素，弹出运算符栈顶元素，计算结果，并压入操作数栈
     * （3）继续操作2
     * @param expression
     * @return
     */
    public int calc(String expression) {
        boolean digitMode = false;
        int digit = 0;

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (Character.isWhitespace(ch)) {
                continue;
            }
            //提取操作数
            if (isDigit(ch)) {
                digitMode = true;
                digit = digit * 10 + (ch - '0');
                if (i == expression.length() - 1) {
                    dataStack.push(digit);
                    digit = 0;
                    digitMode = false;
                }
                continue;
            }
            if (digitMode) {
                dataStack.push(digit);
                digit = 0;
                digitMode = false;
            }

            if (!opLevel.containsKey(ch)) { //跳过非法字符
                continue;
            }

            if (opStack.isEmpty()) { //运算符栈为空，直接压入
                opStack.push(ch);
            } else {
                int curOpLevel = opLevel.get(ch); //当前运算符优先级
                int topOpLevel = opLevel.get(opStack.peek()); //运算符栈顶元素优先级

                if (curOpLevel > topOpLevel) {
                    opStack.push(ch);
                } else {
                    while (!opStack.isEmpty() && curOpLevel <= topOpLevel) {
                        int v1 = dataStack.pop();
                        int v2 = dataStack.pop();
                        char topOp = opStack.pop();

                        int v = calc0(v2, v1, topOp);
                        dataStack.push(v);

                        if (!opStack.isEmpty()) {
                            topOpLevel = opLevel.get(opStack.peek());
                        }
                    }
                    opStack.push(ch);
                }
            }
        }

        while (!opStack.isEmpty()) {
            int v1= dataStack.pop();
            int v2 = dataStack.pop();
            char topOp = opStack.pop();

            int v = calc0(v2, v1, topOp);
            dataStack.push(v);
        }

        return dataStack.pop();
    }

    public static int calc0(int v1, int v2, char op) {
        int result = 0;
        switch (op) {
            case '+':
                result = v1 + v2;
                break;
            case '-':
                result = v1 - v2;
                break;
            case '*':
                result = v1 * v2;
                break;
            case '/':
                result = v1 / v2;
                break;
            case '^':
                result = (int) Math.pow(v1, v2);
                break;
            default:
                break;
        }

        return result;
    }

    public static void main(String[] args) {
        String exp = "1 + 2 + 3";
        String exp2 = "1 + 2 * 3 + 4";
        String exp3 = "23 - 45 + 12 * 4 + 32 - 23 / 2";
        String exp4 = "23 - 45 + 12 * 4 + 32 - 23 / 2 * 2 ^ 3";

        Calculator calculator = new Calculator();
        int r1 = calculator.calc(exp);
        System.out.println(r1);

        r1 = calculator.calc(exp2);
        System.out.println(r1);

        r1 = calculator.calc(exp3);
        System.out.println(r1);

        r1 = calculator.calc(exp4);
        System.out.println(r1);
    }
}
